import java.util.*;

/**
 * 381. O(1) 时间插入、删除和获取随机元素 - 允许重复
 * https://leetcode-cn.com/problems/insert-delete-getrandom-o1-duplicates-allowed/
 */
public class Solutions_381 {
    public static void main(String[] args) {
        RandomizedCollection obj = new RandomizedCollection();
        boolean res1 = obj.insert(4);  // output: true
        System.out.println(res1);
        boolean res2 = obj.insert(3);  // output: true
        System.out.println(res2);
        boolean res3 = obj.insert(4);  // output: false
        System.out.println(res3);
        boolean res4 = obj.insert(2);  // output: true
        System.out.println(res4);
        boolean res5 = obj.insert(4);  // output: false
        System.out.println(res5);
        boolean res6 = obj.remove(4);  // output: true
        System.out.println(res6);
        boolean res7 = obj.remove(3);  // output: true
        System.out.println(res7);
        boolean res8 = obj.remove(4);  // output: true
        System.out.println(res8);
        boolean res9 = obj.remove(4);  // output: true
        System.out.println(res9);
    }
}

class RandomizedCollection {
    Map<Integer, List<Integer>> map = null;
    List<Integer> list = null;

    /** Initialize your data structure here. */
    public RandomizedCollection() {
        map = new HashMap<>();
        list = new ArrayList<>();
    }

    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        list.add(val);
        if (!map.containsKey(val)) {
            // val 在 map 中不存在时
            map.put(val, new ArrayList<>());
        }
        List<Integer> indexs = map.get(val);
        indexs.add(list.size() - 1);
        return indexs.size() == 1;
    }

    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            // val 在 list 中不存在（list 中的元素，都已经记录到了 map 中）
            return false;
        }
        int size = list.size();
        List<Integer> indexs = map.get(val);
        int removeIndex = indexs.remove(0);
        if (removeIndex != size - 1) {
            // 同 list 最后一个元素交换
            int lastNum = list.get(size - 1);
            list.set(removeIndex, lastNum);
            List<Integer> indexs1 = map.get(lastNum);
            // 转换为删除对象，而不是删除索引
            indexs1.remove((Integer) (size - 1));
            indexs1.add(removeIndex);
        }
        // 此时 list 列表的最后一个元素，一定是要删除的 val 元素
        list.remove(size - 1);
        if (indexs.size() == 0) {
            map.remove(val);
        }
        return true;
    }

    /** Get a random element from the collection. */
    public int getRandom() {
        // 随机数索引在 [0, list.size() - 1] 中产生
        return list.get((int) (list.size() * Math.random()));
    }
}


